import java.util.ArrayList;
import java.util.Stack;

/**
 * @author: li_jian
 * @version: 1.0
 * @date: 2020/7/5 22:15
 * @description： @link{https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&&tqId=11156&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking}
 */
public class JZ3_从尾到头打印链表 {

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//        //1、使用栈来实现
//        Stack<Integer> stack = new Stack<>();
//        while (listNode!=null){
//            stack.push(listNode.val);
//            listNode=listNode.next;
//        }
//        ArrayList<Integer> ret = new ArrayList<>();
//        while (!stack.isEmpty()){
//            ret.add(stack.pop());
//        }
//        return ret;

        //2、使用递归来实现
        ArrayList<Integer> ret = new ArrayList<>();
        if (listNode != null) {
            ret.addAll(printListFromTailToHead(listNode.next));

            ret.add(listNode.val);
        }
        return ret;

        //3、头插法，需要创建新链表

    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

